package interview.Algorithms;
import java.util.ArrayList;

import Sorting.Generic;
public class Knapsack {
	
	private int max(int i , int j){
		if (i>=j) return i;
		return j;
	}
	public Iterable<Integer> bestFit(int[] elements , int[] weights , int size){
		int [][] fitMatrix = new int[elements.length+1][size+1];
		int i,j;
		ArrayList<Integer> bestMatch = new ArrayList<Integer>();
		for (i=0; i<=elements.length; i++)
			fitMatrix[i][0]=0;
		
		for (i=0; i<=size; i++)
			fitMatrix[0][i]=0;
		
		Generic.printArray(fitMatrix[0]);
		System.out.println("\n");
		
		for(i=1;i<elements.length;i++){
			for(j=1;j<=size;j++){
				if(weights[i]>j)
					fitMatrix[i][j]=fitMatrix[i-1][j];				
				else{
					fitMatrix[i][j]= max((elements[i]+ fitMatrix[i-1][j-weights[i]]),(fitMatrix[i-1][j]));
				}				
			}
			Generic.printArray(fitMatrix[i]);
			System.out.println("\n");
		}
		j = size;
		i = elements.length-1;
				
		while (j>0  && i>0){
			if(fitMatrix[i][j]>fitMatrix[i-1][j]){
				bestMatch.add(i);
				i = i-1;
				j = j-weights[i];
			}
			else
				i = i-1;
			
		}
		System.out.println(bestMatch);
		return bestMatch;
	}
}
